#include <bits/stdc++.h>
using namespace std;

const long long INF = (1LL<<60);

struct Edge {int u,v,w;};

pair<vector<long long>, bool> bellman_ford(int n, const vector<Edge>& edges, int src){
    vector<long long> dist(n, INF); dist[src]=0;
    for(int i=0;i<n-1;i++){
        bool any=false;
        for(auto &e: edges){
            if(dist[e.u]<INF/2 && dist[e.v] > dist[e.u] + e.w){
                dist[e.v] = dist[e.u] + e.w; any=true;
            }
        }
        if(!any) break;
    }
    // 负环检测
    bool hasNegCycle=false;
    for(auto &e: edges){
        if(dist[e.u]<INF/2 && dist[e.v] > dist[e.u] + e.w){ hasNegCycle=true; break; }
    }
    return {dist, hasNegCycle};
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    // 示例图（可含负权边）
    int n=5; vector<Edge> edges;
    auto add=[&](int u,int v,int w){ edges.push_back({u,v,w}); };
    // 一个无负环的例子
    add(0,1,6); add(0,2,7); add(1,2,8); add(1,3,5); add(1,4,-4);
    add(2,3,-3); add(2,4,9); add(3,1,-2); add(4,3,7); add(4,0,2);

    int src=0; auto [dist, neg] = bellman_ford(n, edges, src);
    if(neg){ cout << "图中存在可达负权环！\n"; }
    cout << "Bellman-Ford 从源点 "<<src<<" 的最短距離:\n";
    for(int i=0;i<n;i++){
        cout << src << " -> " << i << ": ";
        if(dist[i]>=INF/2) cout << "INF\n"; else cout << dist[i] << "\n";
    }
    return 0;
}

